2.8 KB · ⇊ 2 parts · ⤓ Micron 2.8 KB · ⤓ HTML 14.9 KB

top

In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then

c R ( x ) = | { y ∣ ∣ R ( x , y ) } | {\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}

is the corresponding counting function and

# # R = { ( x , y ) ∣ ∣ y ≤ ≤ c R ( x ) } {\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}

denotes the corresponding decision problem.

Note that cR is a search problem while #R is a decision problem, however cR can be C Cook-reduced to #R (for appropriate C) using a binary search (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible).

• Counting complexity class

• See also

• References

• External links

Just as NP has NP-complete problems via many-one reductions, #P has #P-complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.cite-ref-1[1]

• GapP

cite-note-11. ↑ citerefbarak2006Barak, Boaz (Spring 2006). "Complexity of counting" (PDF). Princeton University.

• "counting problem". PlanetMath.

• "counting complexity class". PlanetMath.